package main

import (
	"fmt"
	"go-study/algorithm/common"
)

// 如何合并两个有序链表

func main() {
	head1 := &common.LNode{}
	head2 := &common.LNode{}
	common.CreateNode(head1, []int{1, 3, 5})
	common.CreateNode(head2, []int{2, 4, 6})

	fmt.Println("head1：", head1)
	fmt.Println("head2：", head2)

	head := merge(head1, head2)

	fmt.Println("合并后的链表：", head)
}

func merge(head1 *common.LNode, head2 *common.LNode) *common.LNode {
	if head1 == nil || head1.Next == nil {
		return head2
	}

	if head2 == nil || head2.Next == nil {
		return head1
	}

	current1 := head1.Next
	current2 := head2.Next
	var head, current *common.LNode

	if current1.Data < current2.Data {
		head = head1
		current = current1
		current1 = current1.Next
	} else {
		head = head2
		current = current2
		current2 = current2.Next
	}

	for current1 != nil && current2 != nil {
		if current1.Data < current2.Data {
			current.Next = current1
			current = current1
			current1 = current1.Next
		} else {
			current.Next = current2
			current = current2
			current2 = current2.Next
		}
	}

	if current1 != nil {
		current.Next = current1
	}

	if current2 != nil {
		current.Next = current2
	}

	return head
}
